HW#5 --- last modified January 28 2019 19:27:15..

Solution set.

Due date: May 14

Files to be submitted:
  Hw5.zip

Purpose: To gain experience with NP-completeness proofs and approximation algorithm

Related Course Outcomes:

The main course outcomes covered by this assignment are:

CLO5 -- Given a problem determine within NP that is promised to be either in P or NP-complete prove which it is

CLO7 -- Analyze or code an approximation algorithm for a optimization problem whose decision problem is NP-complete.

Specification:

This homeworks consists of the following written problems, together with a programming exercise described below. Submit the written problems in Hw5.pdf as part of your Hw5.zip file. Submit your code in this ZIP file as well.

1. An almost clique is any graph that is the result of deleting one edge from a clique. Prove that the problem of whether a graph `G` has an almost clique of size `t` is `NP`-complete.
2. Show 0-1-2 integer programming is NP-complete where 0-1-2 integer programming is the problem: Given a list of `m` linear inequalities with rational coefficients over `n` variables `u_1, ... u_n` (i.e., `m` inequalities of the form `a_1u_1 + a_2u_2 + cdots +a_n u_n leq b` where the `a_i` and `b` are fraction `p/q` for some integers `p` and `q`), decide if there is an asssignment of the numbers 0, 1, or 2 to the variables that satisfies all the inequalities.
3. A neural net gate `N\N(x_1, ..., x_n, w_0, w_1,..., w_n)` outputs 1 if `w_0 + sum_i w_ix_i > 0` and 0 otherwise. Here `vec{x_i}` are viewed as the inputs and `vec{w_i}` are called weights. We imagine weights are fixed after some training process. A neural network is a directed acyclic graph where the nodes are labeled with `N\N` gates. The output of such a network is computed in the natural way by evaluating gates which are immediately connected to the inputs, followed by gates all of whose inputs now have values, and so on. Define the neural network understanding (NNU) problem to be given a neural network `N` and a setting for its weights `vec{w}`, decide if there is a setting of its inputs `vec{x}` which makes it output `1`. Show the `N\N\U` problem is `NP`-complete.

For the coding part of the assignment I would like you to code the approximate set cover algorithm discussed in class and submit this in a file ApproxSetCover.java as part of your Hw5.zip file. This program will be compiled from the command line with the syntax:

javac ApproxSetCover.java

java ApproxSetCover some_file_with_list_of_sets.txt

If you decide to use Python, the file should be called ApproxSetCover.py. Here some_file_with_list_of_sets.txt is the name of file that consists of a sequence of lines of ASCII 0's and 1's each of the same length. For example,

1001101
1001000
1001001
1000100
1000000
0000001

Let `n` be the length of a row. Each row represents a subset `S` of the numbers 1, ..., n. A `1` in the `i`th position of a row indicates `i in S` and a `0` indicates `i !in S`. For example, the first row above is the set `S={1,4, 5, 7}`. Your program is supposed to output a set cover of the first row using the remaining rows using the Greedy-Set-Cover algorithm from class. After this it should by brute-force determine a smallest set cover and then output both (greedy-set-cover first) separated by a blank line. For the above example, it should output:

1001001
1000100

1001001
1000100

In class we will show this algorithm is an `r(n)`-approximates the smallest cover where `r(n) = H(max{|S| : S in F})`. Once you have written your program, create some tests cases to see if the Greedy-Set-Cover algorithm does indeed produce `r(n)`-approximations. Write these up in Experiments.txt which you should also include in your Hw5.zip file.

Point Breakdown